package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-27 14:24
 **/
public class LeetCode825 {

    //排序+双指针
    /*public int numFriendRequests(int[] ages) {
        int n = ages.length;
        //升序排列
        Arrays.sort(ages);

        //left:左边界
        int left = 0;
        //right:右边界
        int right = 0;
        //ans:结果
        int ans = 0;

        //题目中的第三个条件包含于第二个条件之中
        //即0.5 * age[x] + 7 < ages[y] <= ages[x],由该表达式可得age[x]必须大于等于15
        for (int age : ages) {

            if (age < 15) {
                continue;
            }

            //将左边界移动到边界值>0.5 * age + 7的位置
            while (ages[left] <= 0.5 * age + 7) {
                ++left;
            }

            //只要下一个元素索引<n且元素值<=age就向右移动一位
            while (right + 1 < n && ages[right + 1] <= age) {
                ++right;
            }

            //将当前元素中可以发送的次数累积到结果ans中,需要减去本身,所以是right - left + 1 - 1 = right - left;
            ans += right - left;
        }
        return ans;
    }*/

    //计数排序+前缀和
    public int numFriendRequests(int[] ages) {
        //由于题目中最大值为120,所以我们直接定义长度为121的数组,使用计数排序,空间换时间
        //cnt[i]:年龄为i的个数
        int[] cnt = new int[121];
        for (int age : ages) {
            ++cnt[age];
        }
        int[] pre = new int[121];
        //计算前缀和, pre[i]: 小于i的元素个数
        for (int i = 1; i <= 120; ++i) {
            pre[i] = pre[i - 1] + cnt[i];
        }
        int ans = 0;
        //age<15没有符合条件的,直接从15开始
        for (int i = 15; i <= 120; ++i) {

            if (cnt[i] > 0) {
                //向下取整
                int bound = (int) (i * 0.5 + 8);
                ans += cnt[i] * (pre[i] - pre[bound - 1] - 1);
            }
        }
        return ans;
    }


    public static void main(String[] args) {
        LeetCode825 code = new LeetCode825();
        System.out.println(code.numFriendRequests(new int[]{16, 17, 18}));
    }

}
